package com.ideaaedi.commonds.tree;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 树化工具类
 *
 * @author <font size = "20" color = "#3CAA3C"><a href="https://gitee.com/JustryDeng">JustryDeng</a></font> <img src="https://gitee.com/JustryDeng/shared-files/raw/master/JustryDeng/avatar.jpg" />
 * @since 1.0.0
 */
@SuppressWarnings({"unused", "SpellCheckingInspection"})
public final class TreeifyUtil {
    
    private TreeifyUtil() {
        throw new UnsupportedOperationException("util-class non-support create instance.");
    }
    
    /* ------------------------------------------ 单父节点树的相关方法 ------------------------------------------ */

    /**
     * 获取指定根节点的树
     *
     * @see TreeifyUtil#treeify(List, Comparator, Object)
     */
    public static <K, T extends Treeify<K, T>> T treeify(List<? extends Treeify<K, T>> nodeList, K nodeKey) {
        return TreeifyUtil.treeify(nodeList, null, nodeKey);
    }

    /**
     * 获取指定根节点的树
     *
     * @param nodeList
     *            需要树化的节点
     * @param childrenComparator
     *            子节点排序器(， 若其不为空，则会对子节点进行排序)
     * @return  指定根节点的树
     */
    public static <K, T extends Treeify<K, T>> T treeify(List<? extends Treeify<K, T>> nodeList, Comparator<? super T> childrenComparator, K nodeKey) {
        return TreeifyUtil.treeify(nodeList, childrenComparator).get(nodeKey);
    }

    /**
     * 获取树map
     * <p>
     * @see TreeifyUtil#treeify(List, Comparator)
     */
    public static <K, T extends Treeify<K, T>> Map<K, T> treeify(List<? extends Treeify<K, T>> nodeList) {
        return TreeifyUtil.treeify(nodeList, (Comparator<? super T>)null);
    }

    /**
     * 获取树map
     * <p>
     * @see TreeifyUtil#treeifyWithSort(List, Comparator)
     */
    public static <K, T extends Treeify<K, T>> Map<K, T> treeify(List<? extends Treeify<K, T>> nodeList, Comparator<? super T> childrenComparator) {
        return TreeifyUtil.treeifyWithSort(nodeList, childrenComparator);
    }

    /**
     * 获取树map
     * <p>
     *     P.S. key-唯一定位节点的key, value-以key对应的节点为根节点的树
     *
     * @param nodeList
     *            需要树化的节点
     * @param childrenComparator
     *            子节点排序器(， 若其不为空，则会对子节点进行排序)
     * @return  树map
     */
    public static <K, T extends Treeify<K, T>> Map<K, T> treeifyWithSort(List<? extends Treeify<K, T>> nodeList, Comparator<? super T> childrenComparator) {
        if (nodeList == null || nodeList.size() == 0) {
            return Maps.newHashMap();
        }
        // 组装map数据
        Map<K, T> treeMap = new HashMap<>(16);
        for (Treeify<K, T> treeify : nodeList) {
            treeMap.put(treeify.obtainNodeKey(), treeify.obtainNewInstance());
        }
        // 组装树形结构
        for (T node : treeMap.values()) {
            T parentNode = treeMap.get(node.obtainParentNodeKey());
            if (Objects.isNull(parentNode)) {
                continue;
            }
            if (parentNode.obtainChildren() == null || parentNode.obtainChildren().size() == 0) {
                parentNode.initChildren();
            }
            parentNode.obtainChildren().add(node);
        }
        // children排序
        if (childrenComparator != null) {
            treeMap.values().forEach(node -> {
                List<T> children = node.obtainChildren();
                if (children == null || children.size() == 1) {
                    return;
                }
                children = children.stream().sorted(childrenComparator).collect(Collectors.toList());
                node.obtainChildren().clear();
                node.obtainChildren().addAll(children);
            });
        }
        return treeMap;
    }

    /**
     * 将树节点node展开为list
     * <P>
     * @see TreeifyUtil#tree2List(Treeify, boolean, boolean, Comparator)
     */
    public static <K, T extends Treeify<K, T>> List<T> tree2List(T node, boolean containSelf, boolean disconnect) {
        return TreeifyUtil.tree2List(node, containSelf, disconnect, null);
    }

    /**
     * 将树节点node展开为list
     *
     * @param node
     *            要展开的tree的根节点
     * @param containSelf
     *            是否包含本身节点
     * @param disconnect
     *            是否断开父子节点之间的children集合联系
     *            <br>注： 此参数的影响范围既包括【参数T】，又包括【结果List<T>】
     * @param comparator
     *            节点排序比较器(， 若其不为空，则会对生成的list进行比较并排序)
     * @return  展开后的list
     */
    public static <K, T extends Treeify<K, T>> List<T> tree2List(T node, boolean containSelf, boolean disconnect, Comparator<? super T> comparator) {
        if(node == null) {
            return Lists.newArrayList();
        }
        List<T> list = new ArrayList<>(16);
        Set<K> existNodeKeySet = new HashSet<>();
        // 是否包含本身节点
        if (containSelf) {
            list.add(node);
            existNodeKeySet.add(node.obtainNodeKey());
        } else {
            existNodeKeySet.add(node.obtainNodeKey());
        }
        Queue<Treeify<K, T>> queue = new LinkedList<>();
        queue.offer(node);
        Treeify<K, T> item;
        List<T> children;
        while (queue.size() > 0) {
            item = queue.poll();
            children = item.obtainChildren();
            if (children == null) {
                continue;
            }
            children= children.stream().filter(x -> !existNodeKeySet.contains(x.obtainNodeKey())).collect(Collectors.toList());
            if (children.size() == 0) {
                continue;
            }
            list.addAll(children);
            existNodeKeySet.addAll(children.stream().map(Treeify::obtainNodeKey).collect(Collectors.toSet()));
            children.forEach(queue::offer);
        }
        // 断开父子节点之间的children集合联系
        if (disconnect) {
            list.forEach(Treeify::disconnectChildren);
        }
        // 排序
        if (comparator != null && list.size() > 1) {
            list = list.stream().sorted(comparator).collect(Collectors.toList());
        }
        return list;
    }

    /**
     * 将树节点node展开为Map
     *
     * @param node
     *            要展开的tree的根节点
     * @param containSelf
     *            是否包含本身节点
     * @param disconnect
     *            是否断开父子节点之间的children集合联系
     *            <br>注： 此参数的影响范围既包括【参数T】，又包括【结果List<T>】
     * @return  展开后的Map
     */
    public static <K, T extends Treeify<K, T>> Map<K, T> tree2Map(T node, boolean containSelf, boolean disconnect) {
        Map<K, T> map = new HashMap<>(16);
        if(node == null) {
            return map;
        }
        Set<K> existNodeKeySet = new HashSet<>();
        // 是否包含本身节点
        if (containSelf) {
            map.put(node.obtainNodeKey(), node);
            existNodeKeySet.add(node.obtainNodeKey());
        } else {
            existNodeKeySet.add(node.obtainNodeKey());
        }
        Queue<Treeify<K, T>> queue = new LinkedList<>();
        queue.offer(node);
        Treeify<K, T> item;
        List<T> children;
        while (queue.size() > 0) {
            item = queue.poll();
            children = item.obtainChildren();
            if (children == null) {
                continue;
            }
            children= children.stream().filter(x -> !existNodeKeySet.contains(x.obtainNodeKey())).collect(Collectors.toList());
            if (children.size() == 0) {
                continue;
            }
            children.stream().filter(Objects::nonNull).forEach(child -> {
                K key = child.obtainNodeKey();
                map.put(key, child);
                existNodeKeySet.add(key);
                queue.offer(child);
            });
        }
        // 断开父子节点之间的children集合联系
        if (disconnect) {
            map.values().forEach(Treeify::disconnectChildren);
        }
        return map;
    }


    /* ------------------------------------------ 多父节点树的相关方法 ------------------------------------------ */

    
    /**
     * 获取指定根节点的树
     *
     * @see TreeifyUtil#treeifyMulti(List, Comparator, Object)
     */
    public static <K, T extends MultiTreeify<K, T>> T treeifyMulti(List<? extends MultiTreeify<K, T>> nodeList, K nodeKey) {
        return TreeifyUtil.treeifyMulti(nodeList, null, nodeKey);
    }
    
    /**
     * 获取指定根节点的树
     *
     * @param nodeList
     *            需要树化的节点
     * @param childrenComparator
     *            子节点排序器(， 若其不为空，则会对子节点进行排序)
     * @return  指定根节点的树
     */
    public static <K, T extends MultiTreeify<K, T>> T treeifyMulti(List<? extends MultiTreeify<K, T>> nodeList, Comparator<? super T> childrenComparator, K nodeKey) {
        return TreeifyUtil.treeifyMulti(nodeList, childrenComparator).get(nodeKey);
    }
    
    /**
     * 获取树map
     * <p>
     * @see TreeifyUtil#treeifyMulti(List, Comparator)
     */
    public static <K, T extends MultiTreeify<K, T>> Map<K, T> treeifyMulti(List<? extends MultiTreeify<K, T>> nodeList) {
        return TreeifyUtil.treeifyMulti(nodeList, (Comparator<? super T>)null);
    }
    
    /**
     * 获取树map
     * <p>
     * @see TreeifyUtil#treeifyMultiWithSort(List, Comparator)
     */
    public static <K, T extends MultiTreeify<K, T>> Map<K, T> treeifyMulti(List<? extends MultiTreeify<K, T>> nodeList, Comparator<? super T> childrenComparator) {
        return TreeifyUtil.treeifyMultiWithSort(nodeList, childrenComparator);
    }
    
    /**
     * 获取树map
     * <p>
     *     P.S. key-唯一定位节点的key, value-以key对应的节点为根节点的树
     *
     * @param nodeList
     *            需要树化的节点
     * @param childrenComparator
     *            子节点排序器(， 若其不为空，则会对子节点进行排序)
     * @return  树map
     */
    public static <K, T extends MultiTreeify<K, T>> Map<K, T> treeifyMultiWithSort(List<? extends MultiTreeify<K, T>> nodeList, Comparator<? super T> childrenComparator) {
        if (nodeList == null || nodeList.size() == 0) {
            return Maps.newHashMap();
        }
        // 组装map数据
        Map<K, T> treeMap = new HashMap<>(16);
        for (MultiTreeify<K, T> node : nodeList) {
            treeMap.put(node.obtainNodeKey(), node.obtainNewInstance());
        }
        // 组装树形结构
        for (T node : treeMap.values()) {
            List<K> parentKeyList = node.obtainParentNodeKey();
            if (parentKeyList == null || parentKeyList.size() == 0) {
                continue;
            }
            for (K parentKey : parentKeyList) {
                T parentNode = treeMap.get(parentKey);
                if (Objects.isNull(parentNode)) {
                    continue;
                }
                if (parentNode.obtainChildren() == null) {
                    parentNode.initChildren();
                }
                parentNode.obtainChildren().add(node);
            }
        }
        // children排序
        if (childrenComparator != null) {
            treeMap.values().forEach(node -> {
                List<T> children = node.obtainChildren();
                if (children == null || children.size() == 1) {
                    return;
                }
                children = children.stream().sorted(childrenComparator).collect(Collectors.toList());
                node.obtainChildren().clear();
                node.obtainChildren().addAll(children);
            });
        }
        return treeMap;
    }
    
    /**
     * 将树节点node展开为list
     * <P>
     * @see TreeifyUtil#multiTree2List(MultiTreeify, boolean, boolean, Comparator)
     */
    public static <K, T extends MultiTreeify<K, T>> List<T> multiTree2List(T node, boolean containSelf, boolean disconnect) {
        return TreeifyUtil.multiTree2List(node, containSelf, disconnect, null);
    }
    
    /**
     * 将树节点node展开为list
     *
     * @param node
     *            要展开的tree的根节点
     * @param containSelf
     *            是否包含本身节点
     * @param disconnect
     *            是否断开父子节点之间的children集合联系
     *            <br>注： 此参数的影响范围既包括【参数T】，又包括【结果List<T>】
     * @param comparator
     *            节点排序比较器(， 若其不为空，则会对生成的list进行比较并排序)
     * @return  展开后的list
     */
    public static <K, T extends MultiTreeify<K, T>> List<T> multiTree2List(T node, boolean containSelf, boolean disconnect, Comparator<? super T> comparator) {
        if(node == null) {
            return Lists.newArrayList();
        }
        List<T> list = new ArrayList<>(16);
        Set<K> existNodeKeySet = new HashSet<>();
        // 是否包含本身节点
        if (containSelf) {
            list.add(node);
            existNodeKeySet.add(node.obtainNodeKey());
        } else {
            existNodeKeySet.add(node.obtainNodeKey());
        }
        Queue<MultiTreeify<K, T>> queue = new LinkedList<>();
        queue.offer(node);
        MultiTreeify<K, T> item;
        List<T> children;
        while (queue.size() > 0) {
            item = queue.poll();
            children = item.obtainChildren();
            if (children == null) {
                continue;
            }
            children= children.stream().filter(x -> !existNodeKeySet.contains(x.obtainNodeKey())).collect(Collectors.toList());
            if (children.size() == 0) {
                continue;
            }
            list.addAll(children);
            existNodeKeySet.addAll(children.stream().map(MultiTreeify::obtainNodeKey).collect(Collectors.toSet()));
            children.forEach(queue::offer);
        }
        // 断开父子节点之间的children集合联系
        if (disconnect) {
            list.forEach(MultiTreeify::disconnectChildren);
        }
        // 排序
        if (comparator != null && list.size() > 1) {
            list = list.stream().sorted(comparator).collect(Collectors.toList());
        }
        return list;
    }
    
    /**
     * 将树节点node展开为Map
     *
     * @param node
     *            要展开的tree的根节点
     * @param containSelf
     *            是否包含本身节点
     * @param disconnect
     *            是否断开父子节点之间的children集合联系
     *            <br>注： 此参数的影响范围既包括【参数T】，又包括【结果List<T>】
     * @return  展开后的Map
     */
    public static <K, T extends MultiTreeify<K, T>> Map<K, T> multiTree2Map(T node, boolean containSelf, boolean disconnect) {
        Map<K, T> map = new HashMap<>(16);
        if(node == null) {
            return map;
        }
        Set<K> existNodeKeySet = new HashSet<>();
        // 是否包含本身节点
        if (containSelf) {
            map.put(node.obtainNodeKey(), node);
            existNodeKeySet.add(node.obtainNodeKey());
        } else {
            existNodeKeySet.add(node.obtainNodeKey());
        }
        Queue<MultiTreeify<K, T>> queue = new LinkedList<>();
        queue.offer(node);
        MultiTreeify<K, T> item;
        List<T> children;
        while (queue.size() > 0) {
            item = queue.poll();
            children = item.obtainChildren();
            if (children == null) {
                continue;
            }
            children= children.stream().filter(x -> !existNodeKeySet.contains(x.obtainNodeKey())).collect(Collectors.toList());
            if (children.size() == 0) {
                continue;
            }
            children.stream().filter(Objects::nonNull).forEach(child -> {
                K key = child.obtainNodeKey();
                map.put(key, child);
                existNodeKeySet.add(key);
                queue.offer(child);
            });
        }
        // 断开父子节点之间的children集合联系
        if (disconnect) {
            map.values().forEach(MultiTreeify::disconnectChildren);
        }
        return map;
    }
}